package huadi.algorithm.sort;

/**
 * 基数排序
 * 
 * @author Huadi
 * @version 2011-09-12
 */
public class RadixSort {
	public static void sort(int[] array) {
		int[] mirrorArray = array;

		for (int digit = 1; digit <= 2; digit++) {
			int[] tempArray = new int[mirrorArray.length];
			int[] bucket = new int[10];

			for (int i = 0; i < tempArray.length; i++)
				tempArray[i] = 0;
			for (int i = 0; i < bucket.length; i++)
				bucket[i] = 0;

			int digitMask = 1;
			for (int i = 0; i < digit; i++)
				digitMask = digitMask * 10; // 由digit决定排序位数的临时变量
			int temp1 = 0;
			int temp2 = 0;
			for (int i = 0; i < mirrorArray.length; i++) {
				temp1 = mirrorArray[i] % digitMask;
				temp1 = temp1 * 10 / digitMask;// 取temp1为当前数指定位数的值

				bucket[temp1] = bucket[temp1] + 1;
			}

			for (int i = 1; i < bucket.length; i++)
				bucket[i] = bucket[i] + bucket[i - 1];
			for (int i = mirrorArray.length - 1; i >= 0; i--) {
				temp1 = mirrorArray[i];
				temp2 = mirrorArray[i] % digitMask;
				temp2 = temp2 * 10 / digitMask;

				tempArray[bucket[temp2] - 1] = temp1;
				bucket[temp2] = bucket[temp2] - 1;
			}
			mirrorArray = tempArray;
		}
		for (int i = 0; i < mirrorArray.length; i++)
			array[i] = mirrorArray[i];
	}

}
